package Demo2_12;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-02-12
 * Time:19:29
 */
import java.util.Stack;

public class StackPushPopOrder {
    public static boolean IsPopOrder(int [] pushA,int [] popA) {
        // 如果两个数组长度不相等，直接返回 false
        if (pushA.length != popA.length) {
            return false;
        }
        // 创建一个辅助栈
        Stack<Integer> stack = new Stack<>();
        // 用于记录 pushA 数组的索引
        int pushIndex = 0;
        // 遍历 popA 数组
        for (int i = 0; i < popA.length; i++) {
            // 当辅助栈为空或者栈顶元素不等于当前要弹出的元素时
            while (stack.isEmpty() || stack.peek() != popA[i]) {
                // 如果 pushA 数组已经遍历完，说明无法继续压栈，跳出循环
                if (pushIndex == pushA.length) {
                    break;
                }
                // 将 pushA 数组中的元素压入辅助栈
                stack.push(pushA[pushIndex]);
                // pushA 数组索引后移
                pushIndex++;
            }
            // 如果栈顶元素等于当前要弹出的元素
            if (stack.peek() == popA[i]) {
                // 弹出栈顶元素
                stack.pop();
            } else {
                // 否则说明该弹出序列不可能是对应的弹出顺序，返回 false
                return false;
            }
        }
        // 如果辅助栈为空，说明该弹出序列是对应的弹出顺序，返回 true
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        int[] pushA = {1, 2, 3, 4, 5};
        int[] popA1 = {4, 5, 3, 2, 1};
        int[] popA2 = {4, 3, 5, 1, 2};
        System.out.println(IsPopOrder(pushA, popA1)); // 输出: true
        System.out.println(IsPopOrder(pushA, popA2)); // 输出: false
    }
}